#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

int swap_count = 0;
int comp_count = 0;

void show(int data[], int len)
{
    int i;
    for(i=0; i<len; ++i)
    {
        printf("%d\t", data[i]);
    }
    printf("\n");
}

void insertionSort(int data[], int len)
{
    if(len <= 1)
        return;

    int i, j;
    for(i=1; i<len; i++)
    {
        int tmp = data[i];

        // 将第i个数，与它前面的 i-1 个数顺序进行比较
        // 可以改进为折半比较，让其从中间折半相比
	int begin=0, end=i-1, mid;
        for(; begin<=end; )
        {
            comp_count++;
	    mid = (begin+end)/2;
            if(data[mid] < tmp)
            {
	    	begin=mid+1;
            }
            else
            {
	    	end=mid-1;
            }
	printf("begin: %d\t", begin);
	printf("mid: %d\t", mid);
	printf("end: %d\n", end);
        }
	for(j=end;data[mid]<tmp?j>mid:j>=mid;j--)
	{
		data[j] = data[j+1];
        	swap_count++;
	}
    }
}

int main(int argc, char **argv)
{
    srand(time(NULL));

    int i, data[100];
    for(i=0; i<100; ++i)
    {
        data[i] = rand() % 1000;
    }
    printf("随机序列: ");
    show(data, 100);

    printf("插入排序: ");
    insertionSort(data, 100);
    show(data, 100);

    printf("总共比较次数: %d\n", comp_count);
    printf("总共移动次数: %d\n", swap_count);

    return 0;
}
